package com.sakura.回溯;

import java.util.HashSet;

public class Code999_字符串全部子序列 {

    public static void main(String[] args) {
        String[] strings = generatePermutation1("abc");
        for (String string : strings) {
            System.out.println(string);
        }
    }

    public static String[] generatePermutation1(String str) {
        char[] s = str.toCharArray();
        HashSet<String> set = new HashSet<>();
        StringBuilder path = new StringBuilder();
        f1(s, 0, path, set);
        String[] ans = new String[set.size()];
        int i = 0;
        for (String str1 : set) {
            ans[i++] = str1;
        }
        return ans;
    }

    private static void f1(char[] s, int i, StringBuilder path, HashSet<String> set) {
        if (i == s.length) {
            set.add(path.toString());
        } else {
            path.append(s[i]);
            f1(s, i + 1, path, set);
            path.deleteCharAt(path.length() - 1);
            f1(s, i + 1, path, set);
        }
    }

}
